\documentclass[a4paper,10pt]{article}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}
\usepackage[francais]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{mathrsfs}
\usepackage{wrapfig}
\usepackage[colorlinks=true,linkcolor=black,urlcolor=blue]{hyperref}
\usepackage[vlined,lined,linesnumbered,boxed,french,longend]{algorithm2e}
\usepackage{xcolor}
\usepackage[top=2.5cm, bottom=2.5cm, left=2cm, right=2cm]{geometry}
\usepackage{lmodern}
\usepackage{enumerate}
\usepackage{verbatim}
\usepackage{multirow}
\usepackage{multicol}
\usepackage{float}
\usepackage{listings}

\lstset{language=SQL, frame=shadowbox}

%partie concernant la gestion des entêtes
\usepackage{fancyhdr}
\lhead{\bsc{Projet de Flot et combinatoire}}
\rhead{\bsc{Conception de réseaux}}
\renewcommand{\headrulewidth}{1px}
\lfoot{ \bsc{Enseirb-Matmeca}}
\rfoot{ \bsc{Informatique-I2}}
\renewcommand{\footrulewidth}{1px}
\pagestyle{fancy}
%fin


%%%%%%%%%%%%%%%% Variables %%%%%%%%%%%%%%%%
\def\titre{Projet de Flot et combinatoire\\{\small Cas d'un problème de conception de réseaux}}
\def\others{ Clément \bsc{Brisset}\\
  Stéphane \bsc{Castelli}\\
  Christian \bsc{Lasserre}\\
  Adele \bsc{Villiermet}
}


\begin{document}
%%%%%%%%%%%%%%%% Header %%%%%%%%%%%%%%%%
\noindent\begin{minipage}{\textwidth}
  \vskip 0mm
  \noindent
  {\begin{tabular}{p{7.5cm}}
      \begin{center}{\itshape \titre\\}\end{center}
    \end{tabular}}
  \hfill
  \fbox{\begin{tabular}{l}
      \others
    \end{tabular}}
  \vskip 8mm ~

  \parbox{\textwidth}{\small \textit{Résumé~:} \sffamily
    Notre étude s'inscrit dans le cadre d'un projet de l'ENSEIRB-MATMECA. Cette étude vise
    à optimiser la solution apportée à un problème de graphe.
    Ce rapport présente les idées que nous avons suivi tout au long du projet ainsi que 
    leur mise en oeuvre.
  }
  \vskip 3mm ~
\end{minipage}


\section*{Introduction}

Pour concevoir un réseau de télécommunication, il faut résoudre un certain 
nombre de problèmes. Dans ce projet nous nous intéressons au cas particulier
de la connexité et de la prévention des pannes. Pour cela, nous devons
élaborer un algorithme qui déterminera quelle topologie doit être mise
en place pour assurer la connexité des terminaux du réseau ainsi que
sa 2-arêtes-connexité. Ainsi, en cas de panne d'un lien, les données
peuvent être acheminées par un autre chemin. Cependant la construction de
réseau étant coûteuse, il est nécessaire d'essayer de minimiser les
coûts de construction en choisissant sa topologie.\\

Ce problème prendra en entrée uniquement des graphes complets.
Cette optimisation devant se faire dans un temps raisonnable, 
nous ne pouvons donc pas utiliser d'algorithmes exponentiels.


\section*{Données et modélisation du problème}
Dans ce rapport les données d'entrées du problème sont notées de la
manière suivante :

\begin{itemize}
\item $V$ : ensemble des terminaux du réseau de cardinal $n \in \mathbb{N}$
\item $E$ : ensemble des liens possibles entre les terminaux 
  (ici on suppose le graphe complet on a donc $E=V*V$)
\item $C$ : la matrice des coûts de construction où $c_{i,j}$ est
  le coût de construction du lien $\{i,j\}$
\item $k \in \{1,...,n\}$ : entier fixant une borne sur la taille des cycles\\
\end{itemize}

L'objectif est donc de choisir les arêtes de $E$  pour que
le réseau final soit connexe et que chacune de ses arêtes appartienne à un
cycle de longueur $\leq k$ tout en minimisant le coût du graphe obtenu.\\

Pour mettre en oeuvre et tester les résultats du projets le site
\href{http://www.math.u-bordeaux1.fr/~ppesneau/cours/combrout/tsp_data.tar.gz}{suivant} 
fournit un ensemble de données sous la forme de coordonnées cartésiennes.
Les noeuds du graphe seront donc identifiés par leur ordre d'apparition
dans le fichier. Les coûts associés aux arêtes seront quand à eux
déduit de la distance cartésienne entre les deux noeuds concernés.
Il va sans dire que l'affichage d'un tel graphe pour une trentaine de noeuds
prend un temps non négligeable et est illisible.

\section*{Un ou Des Algorithmes}
Trouver un résultat optimal à ce problème est difficile c'est pourquoi
l'objectif est ici de trouver une heuristique qui trouve une
''bonne'' solution. Pour cela le projet peut être découpé en sous
problèmes à résoudre séparément.

\subsection*{Connexité}

La première caractéristique à assurer au réseau est la connexité de
tous ses terminaux pour un coût minimal ou un ''bon coût'' si l'on
choisi d'utiliser une heuristique. Ici le calcul d'un arbre couvrant
du réseau garantit sa complexité. C'est pourquoi la première étape de
notre solution est le calcul d'un arbre couvrant minimal à l'aide de
l'algorithme Kruskal. Pour cela nous avons besoin de l'ensemble des
arêtes du graphe triées en fonction de leur coût. Pour ne pas dégrader
la complexité du programme, on effectue un tri par insertion lors de
la récupération des données.
Il suffit ensuite d'appliquer l'algorithme pour obtenir un ACM.\\

\begin{algorithm}[H]
  \Entree{E ensemble des arêtes triées}
  Sélectionner la première arête (celle de coût minimal)\\
  \Tq{toutes les arêtes n'ont pas été traitées}{
    \Si{l'arête sélectionnée ne crée pas de cycle}{
      L'ajouter à L'ACM\\
      Sélectionner l'arête suivante\\
    }
\Sinon{Sélectionner l'arête suivante}
}
\caption{Kruskal}
\end{algorithm}


\subsection*{2-arêtes-connexité}

Pour mettre en place la fiabilité du réseau en cas de panne, il faut
s'assurer qu'entre toute paire de sommets il existe 2 chemins
arête-disjoints. Il s'agit du problème de la 2-arêtes-connexité. Il
faut donc à partir de l'ACM obtenu précédemment ajouter des arêtes
afin que toutes les arêtes du réseau appartiennent à un cycle de
longueur bornée par $k$.\\

Le problème de la mise en place de la 2-arêtes-connexité peut
également être coupé en 2 sous-problèmes :
\begin{itemize}
\item la construction d'un ensemble de cycles sur ce graphe
\item un problème de couverture du réseau par des cycles de cet ensemble.\\
\end{itemize}

Néanmoins, les algorithmes que nous avons mis en place ne tiennent pas compte
de cette séparation. En effet, le problème de couverture demande le calcul
d'un ensemble de cycle ce qui est gourmand en temps. Nous parlons au pluriel
car nous avons vraiment voulu se faire confronter plusieurs idées dans ce rapport.\\

Les deux méthodes que nous allons présenter par la suite ont un point commun :
elles retournent toute les deux un résultat correct. Cela n'est pas anodin puisque
l'on pourrait vouloir comparer des algorithmes qui soient plus rapide et plus lâche sur la 
correction de l'algorithme. Mais comme notre sujet spécifiait bien ``une solution'',
nous avons mis l'accent sur la correction des algorithmes que nous proposons.\\

\section*{Méthode 1}
Le principe, tout comme pour la seconde méthode, débute avec un Arbre
Couvrant Minimal.  L'idée est simple : on ajoute des arêtes, en
essayant de minimiser leur coût, à l'ACM afin de créer des cycles. Le
tout va se faire par un parcours des sommets de l'ACM.\\
En partant d'un
sommet, on construit une première boucle en avançant dans l'arbre par
les branches de coût minimal.  Si l'on se retrouve sur un endroit
isolé de l'ACM, on ferme la boucle à l'endroit initial.  Une autre
version a été tentée en continuant a regarder sur d'autre branches de
l'arbre couvrant.  Mais dans les deux cas, la longueur des boucles
n'est pas réfléchie.  Cela nous permet d'être rapide mais nous empêche
d'être rigoureux.  Ce sont deux heuristiques différentes.\\

\begin{algorithm}[H]
\SetKwFunction{Union}{Union}\SetKwFunction{FindCompress}{FindCompress}
  \SetKwInOut{Input}{Entrée}
  \SetKwInOut{Output}{Sortie}
  \Input{$G = (E,V)$ :: graphe connexe}
  \Output{$E'$ :: ensemble des arêtes d'une solution}
  \BlankLine
  \BlankLine

  $ACM \leftarrow calculACM(G)$\\
  $RES \leftarrow ACM$\\
  $AVISITER \leftarrow V$\\
  \Tq{$AVISITER \neq \emptyset$}{
    $ini \leftarrow pop~(AVISITER)$\\
    $noeudCourant \leftarrow ini$\\
    $i \leftarrow 0$\\

    \Tq{$i < k$ et $AVISITER \neq \emptyset$}{
      $prochainNoeud \leftarrow voisinNonVisiteDansACM()$\\
      \Si{$aucunVoisinNonVisite~(prochainNoeud)$}{
        $prochainVoisin \leftarrow \leftarrow popEnCherchantLeCoutADistanceMinimum~(AVISITER, noeudCourant)$\\
        $RES \leftarrow RES \cup \{\{noeudCourant,prochainNoeud\}\}$\\
        $noeudCourant \leftarrow prochainVoisin$
      }
      \Sinon{
        $retirer(AVISITER, prochainNoeud)$\\
        $RES \leftarrow RES \cup \{\{noeudCourant,prochainNoeud\}\}$\\
      }
      $i += 1$\\
    }

    $RES \leftarrow RES \cup \{\{ini,prochainNoeud\}\}$\\
  }
  
\end{algorithm}

Cet algorithme nous permet ainsi d'impliquer chaque noeud dans au plus 2 cycles. La gestion de certains cas
peut en fait nous amener à en avoir plus. Si, par exemple, après avoir attaché tous les noeuds du graphe à
un cycle, il reste un noeud isolé et qu'on le rattache à un noeud déjà au centre de deux cycles.\\
D'autre part, les coûts ``devraient approcher'' le minimum car ils sont minimisé pour chaque cycle.
Néanmoins, la longueur des cycles est le seul facteur qui n'est pas discuté dans cet algorithme et qui
peut s'y opposer. Si de plus petits cycles permettent de diminuer le coût global du réseau,
notre algorithme ne saura le détecter.



% Le principe, tout comme pour la seconde méthode, débute avec un Arbre Couvrant Minimal.
% L'idée est plutôt simple en fait  : on ajoute des arêtes, à plus faible coût,
% à l'ACM. Le tout va se faire par un parcours linéaire de l'ACM. En effet, pour choisir quel noeud
% choisir pour faire une boucle, on choisi un noeud voisin dans l'ACM. Si ce noeud est isolé dans ce qui
% reste de l'ACM, \\

% \begin{algorithm}[H]
%   \SetKwFunction{Union}{Union}\SetKwFunction{FindCompress}{FindCompress}
%   \SetKwInOut{Input}{Entrée}
%   \SetKwInOut{Output}{Sortie}
%   \Input{$G = (E,V)$ :: graphe connexe}
%   \Output{$E'$ :: ensemble des arêtes d'une solution}
%   \BlankLine
%   \BlankLine
  
%   $ACM \leftarrow calculACM(G)$\\
%   $RES \leftarrow ACM$\\
%   $AVISITER \leftarrow V$\\
%   \Tq{$AVISITER \neq \emptyset$}{
%     $ini \leftarrow pop~(AVISITER)$\\
%     $noeudCourant \leftarrow ini$\\
%     $i \leftarrow 0$\\
    
%     \Tq{$i < k$ et $AVISITER \neq \emptyset$}{
%       $prochainNoeud \leftarrow voisinNonVisiteDansACM()$\\
%       \Si{$aucunVoisinNonVisite~(prochainNoeud)$}{
%         $prochainVoisin \leftarrow \leftarrow popEnCherchantLeCoutADistanceMinimum~(AVISTER, noeudCourant)$
%         $RES \leftarrow RES \cup \{\{noeudCourant,prochainNoeud\}\}$
        
%         %$noeudCourant = prochainVoisin$
%       }
%       \Sinon{
%         $RES \leftarrow RES \cup \{\{noeudCourant,prochainNoeud\}\}$
%       }
%       $i += 1$
%     }
    
%   }
%   \caption{Kruskal} 
% \end{algorithm}








\section*{Méthode 2}
%REPARLER DE 2-ARETE-CONNEXITE ! (dsl d'avoir effacer un peu ^^)
%pas 2 algo séparés mais traite un peu comme ça qd mm

Cette méthode bien que n'ayant pas deux algorithmes séparés pour
traiter des sous-problèmes décrits plus haut s'inspire de cette
séparation. En effet, à chaque cycle de l'algorithme, celui-ci se
sépare en 2 sous-traitements s'inspirant des 2 problèmes cités.\\

A chaque étape une arête est sélectionnée :\\

\begin{algorithm}[H]
  \Entree{F ensemble des feuilles\\
    ACM arbre couvrant calculé précédemment}
  \Tq{la solution ne contient pas toutes les arêtes de ACM}{
    \Si{$\exists\ a$ arête de ACM telle que $a$ est incidente à une feuille}{
      Sélectionner a\\
    }
    \Sinon{Sélectionner une arête de ACM}
  }
  \caption{choix arête}
\end{algorithm}


A partir de cette arête, on construit un ensemble de cycles candidats la contenant.
Pour pouvoir comparer différents cycles possibles et choisir lequel
ajouter au graphe, il faut choisir une métrique de comparaison.
Pour l'heuristique présentée ici, cette métrique est :

$$\frac{co\hat{u}t\ de\ l'arc\ ajout\acute{e}}{nombre\ d'arcs\ s\acute{e}lectionn\acute{e}s\ n'appartenant\ encore\ \grave{a}\ aucun\ cycle}$$

Le but étant de minimiser le coût de construction du réseau, nous
cherchons à minimiser ce rapport. Le dénominateur permet de
privilégier les cycles ayant le moins d'arêtes déjà traitées.\\

\begin{algorithm}[H]
  \Entree{$\{i,j\}$ arête sélectionnée\\
    ACM\\
    }
  $ct \leftarrow 0$\\
  $A \leftarrow \emptyset$\\
  \Tq{$ct<k$}{
    \Si{$\exists$ une arête incidente à $j$ appartenant à ACM}{
      Choisir $\{j,d\}$ telle que $m\acute{e}trique$ soit minimale\\
      Ajouter $(\{j,d\},ct)$ à $A$\\
      $j \leftarrow d$\\
      $ct \leftarrow ct+1$\\
    }
    \Sinon{terminer la boucle}
  }
  $C \leftarrow \emptyset$\\
  $\forall\ (\{i_k,i_{k+1}\},ct) \in A$\\
  //par leur construction tous les éléments de $A$ vont être traités\\
  ajouter le cycle $\{\{i,i_1\},\{i_1,i_2\},,\{i_{ct-1},i_{ct}\},\{i_{ct},i\}\}$ à $C$\\
\Sortie{$C$}
  \caption{cycles candidats}
\end{algorithm}

Parmi ces candidats, un cycle est choisi pour être ajouté à la solution, celui
pour lequel la métrique décrite précédemment est minimale.\\

Comme on s'assure par la condition d'arrêt de la boucle initiale que
toutes les arêtes de l'ACM feront partie d'un cycle dans la solution
retenue, on peut être certain d'obtenir une solution au problème
posé.\\ 
Pour cette heuristique, les résultats dépendent du choix de
parcours du graphe et les critères pour la sélection des cycles
candidats. Une optimisation de notre algorithme passerais donc par un
travail sur cette sélection.



%ensemble arêtes traitées/arêtes pas traitées ?
%description de l'algo

\section*{Conclusion}
\addcontentsline{toc}{section}{Conclusion}

Nous avons réfléchi à deux solutions différentes pour résoudre ce
problème bien qu'une seule ait réellement aboutie.  En effet, nous
n'avons pas réussi à faire fonctionner la première méthode implémentée
en python. En revanche, la deuxième méthode, implémentée en C++, est
fonctionnelle.  Une étude des résultats obtenus nous auraient
certainement fourni des pistes d'amélioration de l'heuristique mais le
temps nous a manqué.\\

Pour conclure, ce projet nous a permis de visualiser la
complexité de problèmes concrets et l'importance des réflexions
heuristiques pour les résoudre.

\end{document}
